package com.datastructure.test.rotapple;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class RotApple {

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> grid = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(1);
        list.add(1);
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(0);
        list1.add(1);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(1);
        list2.add(1);
        grid.add(list);
        grid.add(list1);
        grid.add(list2);
        RotApple rotApple = new RotApple();
        int apple = rotApple.rotApple(grid);
        System.out.println(apple);
    }
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        int[][] map = new int[grid.size()][grid.get(0).size()];
        int good = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = grid.get(i).get(j);
            }
        }
        Queue<int[]> que = new LinkedList<int[]>();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if(map[i][j]==2)
                    que.add(new int[] {i,j});
                if(map[i][j]==1) {
                    boolean has = false;
                    int[][] vec = new int[][] {{1,0},{-1,0},{0,1},{0,-1}};
                    for (int k = 0; k < vec.length; k++) {
                        int nx = i+vec[k][0];
                        int ny = j+vec[k][1];
                        if(nx<0||ny<0||nx>=map.length||ny>=map[0].length||map[nx][ny]==0)
                            continue;
                        has = true;
                    }
                    if(!has) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                    good++;
                }
            }
        }

        int ans = 0;

        while(good>0) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] pos = que.poll();
                int x = pos[0];
                int y = pos[1];
                int[][] vec = new int[][] {{1,0},{-1,0},{0,1},{0,-1}};
                for (int k = 0; k < vec.length; k++) {
                    int nx = x+vec[k][0];
                    int ny = y+vec[k][1];
                    if(nx<0||ny<0||nx>=map.length||ny>=map[0].length||map[nx][ny]!=1)
                        continue;
                    map[nx][ny] = 2;
                    que.offer(new int[] {nx, ny});
                    good--;
                }
            }
            ans++;
        }

        return ans;
    }

}
